//合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 
//
// 示例: 
//
// 输入:
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//输出: 1->1->2->3->4->4->5->6 
// Related Topics 堆 链表 分治算法


package leetcode.d_1_99;

import java.util.PriorityQueue;
import java.util.Queue;

//Java：合并K个排序链表
public class P23MergeKSortedLists{
    public static void main(String[] args) {
        Solution solution = new P23MergeKSortedLists().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length < 0){
                return null;
            }
            if (lists.length == 1){
                return lists[0];
            }
            Queue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
            ListNode res = new ListNode(-1);
            ListNode tail = res;
            for (ListNode listNode : lists) {
                if (listNode == null){
                    continue;
                }
                queue.offer(listNode);
            }
            while (!queue.isEmpty()){
                ListNode minNode = queue.poll();
                tail.next = minNode;
                tail = tail.next;
                if (minNode.next != null){
                    queue.offer(minNode.next);
                }
            }
            return res.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}